package lib

//link to 81
func init() {
	Probs = append(Probs, Problem{
		Num:         33,
		Discription: "搜索无重复元素的旋转数组",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
		},
	})
}

// Search 对半查找，一半是有序递增，另一半无序，如果target在有序的那一半的范围，继续对半查找有序的一半，否则查找无序的一半
//  @param nums
//  @param target
//  @return int
func Search(nums []int, target int) int {
	left := 0
	right := len(nums) - 1
	for left <= right {
		//防止溢出
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		}

		//判断哪一边有序
		//一定要等于！！考虑到left==mid的情况
		if nums[left] <= nums[mid] {
			if nums[left] <= target && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && target <= nums[right] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return -1
}